package com.cris.search;

/**
 * Created by owen on 2017/3/30.
 */

/**
 * 二叉查找树，这里面的有些细节是值得多久品味的
 * @param <Key>
 * @param <Value>
 */
public class BST <Key extends Comparable<Key>,Value> {
    private Node root;
    private class Node{
        Node left,right;
        Key key;
        Value val;
        int N;
        public Node(Key key,Value val,int N){
            this.key=key;
            this.val = val;
            this.N = N;
        }
    }
    public int size(){
        return size(root);
    }
    private int size(Node x){
        if(root==null) return 0;
        else return x.N;
    }
    public Value get(Key key){
        return get(root,key);
    }

    /**
     * 查找
     * @param x
     * @param key
     * @return
     */
    private Value get(Node x,Key key){
        if(x==null) return null;
        int cmp = key.compareTo(x.key);
        if(cmp<0) return get(x.left,key);
        else if (cmp>0) return get(x.right,key);
        else return x.val;
    }
    public void put(Key key,Value val){
        root = put(root,key,val);
    }
    private Node put(Node x,Key key,Value val){
        if(x==null) return new Node(key,val,1);
        int cmp = key.compareTo(x.key);
        if(cmp<0) put(x.left,key,val);
        else if(cmp > 0) put(x.right,key,val);
        else x.val=val;
        x.N = size(x.left)+size(x.right)+1;
        return x;
    }
    public Key min(){
        return min(root).key;
    }
    private Node min(Node x){
        if(x.left==null) return x;
        return min(x.left);
    }
    public Key Max(){
        return max(root).key;
    }
    private Node max(Node x){
        if(x.right==null) return x;
        return min(x.right);
    }
    public Key floor(Key key){
        Node x = floor(root,key);
        if(x==null) return null;
        return x.key;
    }
    private Node floor(Node x,Key key){
        if(x==null) return null;
        int cmp = key.compareTo(x.key);
        if(cmp<0) return floor(x.left,key);
        Node t = floor(x.right,key);
        if(t!=null) return t;
        else return x;
    }
    public Key select(int k){
        Node x = select(root,k);
        if(x==null) return null;
        return x.key;
    }
    private Node select(Node x,int k){
        if(x==null) return null;
        int t = size(x.left);
        if(t<k) return select(x.right,k-t-1);
        else if(t>k) return select(x.left,k);
        else return x;
    }
    public int rank(Key key){
        return rank(root,key);
    }
    private int rank(Node x,Key key){
        if(x==null) return 0;
        int cmp = key.compareTo(x.key);
        if(cmp<0) return rank(x.left,key);
        else if(cmp>0) return 1+size(x.left)+rank(x.right,key);
        else return size(x.left);
    }
    public void delete(Key key){
        // TODO: 2017/3/30
    }

}

